package com.liang.leetcode.array;

/**
 * 34.在排序数组中查找元素的第一个和最后一个位置
 * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/">https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/</a>
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 */
public class Array07_SearchRange {
    public static void main(String[] args) {
        int[] nums = {5, 8, 8, 9, 10};
        int target = 8;
        int[] range = searchRange(nums, target);
        System.out.println(range[0]);
        System.out.println(range[1]);
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] range = {-1, -1};
        if (nums == null || nums.length == 0) {
            return range;
        }
        // 获取 target 的开始位置
        int left = getBorder(nums, target);
        // target 不存在
        if (left >= nums.length || nums[left] != target) {
            return range;
        }
        range[0] = left;
        // target 存在，继续找结束位置
        int right = left;
        while (right < nums.length && nums[right] == target) {
            right++;
        }
        // right 指向第一个不等于 target 的值
        range[1] = right - 1;
        return range;
    }

    // 获取目标值在有序数组边界上的索引
    public static int getBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
